In many storage systems, data is stored under encryption utilizing one or more cryptographic keys, which are more generally referred to herein as “master keys.” However, problems can arise in such systems in regard to “shredding” of stored encrypted data items, where shredding generally refers to effectively rendering unreadable or otherwise deleting a given stored encrypted data item through deletion of its associated master key. More particularly, shredding of stored encrypted data items under conventional practice can be unduly complex, in that it typically involves decryption of all data items to be retained followed by corresponding re-encryption of the retained data items using a new master key. This can significantly undermine the performance of the storage system, particularly for systems that store large amounts of data or are subject to frequent deletion of data items.